graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the shuffle-exchange network is an

undirected In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

cubic

multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...

, whose vertices represent

binary sequence A bitstream (or bit stream), also known as binary sequence, is a sequence of bits. A bytestream is a sequence of bytes. Typically, each byte is an 8-bit quantity, and so the term octet stream is sometimes used interchangeably. An octet may ...

s of a given length and whose edges represent two operations on these sequence,

circular shift In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse oper ...

s and flipping the lowest-order bit.

Definition

In the version of this network introduced by Tomas Lang and Harold S. Stone in 1976, simplifying earlier work of Stone in 1971, the shuffle-exchange network of order

d

consisted of an array of

2^d

cells, numbered by the

2^d

different

binary number A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one). The base-2 numeral system is a positional notatio ...

s that can be represented with

d

bits. These cells were connected by communications links in two different patterns: "exchange" links in which each cell is connected to the cell numbered with the opposite value in its lowest-order bit, and "shuffle" links in which each cell is connected to the cell whose number is obtained by a

that shifts every bit to the next more significant position, except for the highest-order bit which shifts into the lowest-order position. The "exchange" links are bidirectional, while the "shuffle" links can only transfer information in one direction, from a cell to its circular shift. Subsequent work on networks with this topology removed the distinction between unidirectional and bidirectional communication links, allowing information to flow in either direction across each link.

Applications

The advantage of this communications pattern, over earlier methods, is that it allows information to be rapidly transferred through a small number of steps from any vertex in the network to any other vertex, while only requiring a single bit of control information (which of the two communications links to use) for each communications step. Fast parallel algorithms for basic problems including

sorting Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. # ordering: arranging items in a sequence ordered by some criterion; # categorizing: grouping items with similar pro ...

matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...

, polynomial evaluation, and

Fourier transform A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed, ...

s are known for parallel systems using this network.

Layout area

If this network is given a straightforward layout in the

integer lattice In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid ...

, with the vertices placed on a line in numerical order, with each lattice edge carrying part of at most one communication link, and with each vertex or crossing of the network placed at a lattice point, the layout uses area

O(2^)

, quadratic in its number of vertices. However, more compact and asymptotically optimal layouts with area

O(2^/d^2)

were described by F. Thomson Leighton in his 1981 doctoral dissertation.

Related networks

A related communications network, the "omega network" or

multi-stage A multistage rocket or step rocket is a launch vehicle that uses two or more rocket ''stages'', each of which contains its own engines and propellant. A ''tandem'' or ''serial'' stage is mounted on top of another stage; a ''parallel'' stage is ...

shuffle-exchange network, consists of a given number of stages, each consisting of

2^d

vertices, with the shuffle links connecting pairs of vertices in consecutive stages and the exchange links connecting pairs of vertices in the same stage as each other. The same operations on binary words, of rotation and flipping the first bit, can also be used to generate the

cube-connected cycles In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by for use as a network topology in parallel computing. Definition The cube-connected c ...

, a different cubic parallel communications network with a greater number of vertices. Instead of having the binary words themselves as its vertices, the vertices of the cube-connected cycles represent operations on words that can be generated by rotation and flipping, and the edges represent the composition of one of these operations with an additional rotation or flip.

References

{{reflist, refs= {{citation , last1 = Annexstein , first1 = Fred , last2 = Baumslag , first2 = Marc , last3 = Rosenberg , first3 = Arnold L. , author3-link = Arnold L. Rosenberg , title = Group action graphs and parallel architectures , journal = SIAM Journal on Computing , volume = 19 , issue = 3 , pages = 544–569 , year = 1990 , doi = 10.1137/0219037 {{citation , last1 = Graham , first1 = Niall , last2 = Harary , first2 = Frank , author2-link = Frank Harary , doi = 10.1016/0895-7177(93)90255-W , issue = 11 , journal = Mathematical and Computer Modelling , mr = 1236511 , pages = 69–74 , title = Hypercubes, shuffle-exchange graphs and de Bruijn digraphs , volume = 17 , year = 1993, doi-access = free {{citation , last = Lawrie , first = Duncan H. , doi = 10.1109/t-c.1975.224157 , issue = 12 , journal = IEEE Transactions on Computers , mr = 383864 , pages = 1145–1155 , title = Access and alignment of data in an array processor , volume = C-24 , year = 1975 {{citation , last = Leighton , first = F. Thomson , author-link = F. Thomson Leighton , mr = 2941014 , publisher = Massachusetts Institute of Technology , title = Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI , type = Ph.D. dissertation , url = https://apps.dtic.mil/dtic/tr/fulltext/u2/a121538.pdf , archive-url = https://web.archive.org/web/20210227015043/https://apps.dtic.mil/dtic/tr/fulltext/u2/a121538.pdf , url-status = live , archive-date = February 27, 2021 , via = Defense Technical Information Center , year = 1981 {{citation , last1 = Lang , first1 = Tomas , last2 = Stone , first2 = Harold S. , date = January 1976 , doi = 10.1109/tc.1976.5009205 , issue = 1 , journal = IEEE Transactions on Computers , pages = 55–65 , title = A shuffle-exchange network with simplified control , volume = C-25 {{citation , last = Stone , first = H.S. , date = February 1971 , doi = 10.1109/t-c.1971.223205 , issue = 2 , journal = IEEE Transactions on Computers , pages = 153–161 , publisher = Institute of Electrical and Electronics Engineers ({IEEE}) , title = Parallel processing with the perfect shuffle , volume = C-20 Network topology Parametric families of graphs Regular graphs